package week_8.实验二_树;

 import java.util.*;
    public class InfixToPostfixTree {
        public Stack<LinkedBinaryTree> operand;   // 操作数栈
        public Stack<String> operator;    // 运算符栈
        public String result = "";

        public InfixToPostfixTree()
        {
            operand = new Stack<LinkedBinaryTree>();
            operator = new Stack<String>();
        }

        public LinkedBinaryTree getOperand(Stack<LinkedBinaryTree> treeStack)
        {
            LinkedBinaryTree temp = treeStack.pop();

            return temp;
        }

        public String convert(String infixline) {
            LinkedBinaryTree operand1;
            LinkedBinaryTree operand2;
          //用两个二叉树
            StringTokenizer stringTokenizer = new StringTokenizer(infixline);

            String tempvalue;

            while (stringTokenizer.hasMoreTokens()) {
                tempvalue = stringTokenizer.nextToken();

                // 优先处理括号
                if (tempvalue.equals("(")) {
                    operator.push(tempvalue);
                    tempvalue = stringTokenizer.nextToken();

                    while (!tempvalue.equals(")")) {
                        if (tempvalue.equals("+") || tempvalue.equals("-")) {
                            if (!operator.isEmpty()) {
                                // 运算符栈不为空，继续判断“(”
                                if (operator.peek().equals("("))
                                    operator.push(tempvalue);
                                else {
                                    String b = operator.pop();
                                    operand1 = getOperand(operand);
                                    operand2 = getOperand(operand);
                                    LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                                    operand.push(a);
                                    operator.push(tempvalue);
                                }
                            } else {
                                // 栈为空，运算符入栈
                                operator.push(tempvalue);
                            }
                        } else if (tempvalue.equals("*") || tempvalue.equals("/")) {
                            if (!operator.isEmpty()) {
                                if (operator.peek().equals("*") || operator.peek().equals("/")) {
                                    String b = operator.pop();
                                    operand1 = getOperand(operand);
                                    operand2 = getOperand(operand);
                                    LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                                    operand.push(a);
                                    operator.push(tempvalue);
                                } else {
                                    operator.push(tempvalue);
                                }
                            }
                        } else {
                            // 操作数入栈
                            LinkedBinaryTree a = new LinkedBinaryTree(tempvalue);
                            operand.push(a);
                        }
                        tempvalue = stringTokenizer.nextToken();
                    }

                    while (true) {
                        String b = operator.pop();
                        if (!b.equals("(")) {
                            operand1 = getOperand(operand);
                            operand2 = getOperand(operand);
                            LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                            operand.push(a);
                        }
                        else {
                            break;
                        }
                    }
                }
                else if (tempvalue.equals("+") || tempvalue.equals("-")) {
                    if (!operator.isEmpty()) {
                        String b =  operator.pop();
                        operand1 = getOperand(operand);
                        operand2 = getOperand(operand);
                        LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                        operand.push(a);
                        operator.push(tempvalue);
                    } else {
                        operator.push(tempvalue);
                    }
                } else if (tempvalue.equals("*") || tempvalue.equals("/")) {
                    if (!operator.isEmpty()) {
                        if (operator.peek().equals("*") || operator.peek().equals("/"))
                        {
                            String b = operator.pop();
                            operand1 = getOperand(operand);
                            operand2 = getOperand(operand);
                            LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                            operand.push(a);
                            operator.push(tempvalue);
                        }
                        else
                        {
                            operator.push(tempvalue);
                        }
                    }else {
                        operator.push(tempvalue);
                    }
                }
                else
                {
                    LinkedBinaryTree a = new LinkedBinaryTree(tempvalue);
                    operand.push(a);
                }
            }

            while (!operand.isEmpty() && !operator.isEmpty()) {
                String b = operator.pop();
                operand1 = getOperand(operand);
                operand2 = getOperand(operand);
                LinkedBinaryTree a = new LinkedBinaryTree(b, operand2, operand1);
                operand.push(a);
            }
            System.out.println("前缀表达式为："+infixline);
            System.out.println("输出后缀表达式树：");
            System.out.println(operand.peek().toString());
            Iterator postfixTree = operand.pop().iteratorPostOrder();


            System.out.println("对应的后缀表达式为：");
            while (postfixTree.hasNext()) {
                result += postfixTree.next()+" ";
            }
            return result;
        }

    }


